A typical packet network 1 is illustrated in FIG. 1, showing a few exemplary nodes and links. Nodes 10, 12, 14, and 16 are interior nodes, which have no connections outside the network, and nodes 18, 20, and 22 are edge nodes. The network has interior links 24, 26, 28, 30, 32, 34, 36, 38, 40, and 42, each link joining a pair of nodes, and external links 44, 46, and 48 going outside of the network.
User packet traffic enters and leaves the network over the external links 44, 46, and 48 at edge nodes 18, 20, and 22 respectively. Packets of a particular packet stream are forwarded from the edge node where they enter (a source node), through one or more interior nodes to the edge node where they leave (a destination node).
A schematic view 50 of the network 1 of FIG. 1 is illustrated in FIG. 2, showing a division of the network 1 into a control plane 100 and a data plane 102. Each node and link of the network has a representation in the control plane as well as in the data plane. The Control Plane 100 shows the logical representation of the network, held in the data tables of computing means 106 associated with each node (but not necessarily residing at the nodes), and the algorithms running in the computing means 106. The data plane 102 shows the physical resources needed to process and forward packets.
In more detail, the computing means 106 includes a Routing function 108 comprising a Link State Data Base (LSDB) 112, and a Protection function 110. A copy of LSDB 112 exists in the control plane 100 of each node, and uniquely determines the network topology. Normally, the contents of the LSDB 112 at each node are identical. The Routing function 108 uses the LSDB 112 to generate forwarding tables specific to each node. The Protection function 110 is a local function at each node to monitor links and update the (local) LSDB 112 and Routing function 108 when failures occur or are recovered from. The Routing function 108 then ensures that these changes are propagated to all other nodes in the network, in order that the LSDBs 112 at each node are again a representation of the true state of the network.
The Data Plane 102 contains the Transmission function 111, which includes the ability to detect link failures (Failure Detection 113), and Forwarding function 114 (which includes Look Up Tables (LUT) 116 and Switching 117).
The Transmission function 111 in the Data Plane 102 is linked to the Protection function 110 in the Control Plane 100. This link serves to report link failures detected by the Transmission function 111 to the Protection function 110.
The Routing function 108 in the Control Plane 100 is linked to the Forwarding function 114 in the Data Plane 102. This link serves to load the Look Up Tables (LUT) 116 in the Forwarding function 114 from the forwarding tables computed by the Routing function 108 of the computing means 106.
The path taken by the packets from the source node to the destination node is determined in the source node (source-routing). This is made possible by a routing protocol such as OSPF (Open Shortest Path First, described, e.g. in IETF document rfc2328), which distributes the network topology information to LSDBs 112 at the nodes. Normally, the LSDBs 112 of all nodes contain the same information through the operation of OSPF.
However, when a link fails, the information in the LSDBs 112 is temporarily incorrect until OSPF in the node adjacent to the failed link discovers the failure, and distributes updated LSDB information to the other nodes. The OSPF method of maintaining correct link state information runs in the distributed control plane 100 of the network 1, and requires a long time (up to several seconds in large networks) before all nodes have the updated LSDB 112 information after a link or node failure. Until that time, some packets continue to be lost if they are routed over a path that includes the failed link. Node failures can be treated like link failures, where each of the links to or from the failed node appears to have failed simultaneously. Again, the adjacent nodes discover the failure, update their own LSDBs, and distribute the information to the rest of the network via OSPF protocol, which is slow.
Although in a network offering traditional best effort packet services only, lost packets cause a deterioration in the service but are often recovered by the users, however, in networks offering high levels of service reliability, or offering packetized circuit emulation services, such a situation is not acceptable.
To solve this problem, it has been suggested to use a reliable physical layer in the network through the use of spare links and to provide an automatic protection switching at that layer. Where such systems are used, the OSPF routing layer is prevented from discovering failed links, because through its protection mechanism, the physical layer substitutes working links on a very short time scale, typically of the order of 10 to 50 milliseconds. Time delays built into OSPF are designed to bridge such short outages precisely, because the rapid recovery at the link layer is expected. Earlier physical layer protection systems used parallel links in a 1:1 or 1:N redundancy configuration. More recently, physical layer link protection schemes have been proposed, which use rings or mesh networks. One example of a physical layer protection scheme is an optical ring proposal, which can be found in an IETF (Internet Engineering Task Force) draft [IETF draft-papadimitriou-optical-rings-00.txt]. Another mesh network restoration scheme using spare links is described in U.S. Pat. No. 4,956,835 (“Method and Apparatus for Self-Restoring and Self-Provisioning Communication Networks”) to W. Grover, improvements to which are further described in U.S. Pat. No. 5,862,125 (“Automated Restoration of Un-Restored Link and Nodal Failures”) to W. Russ and U.S. Pat. No. 5,850,505 (“Method for Preconfiguring a Network to Withstand Anticipated Failures”) to W. Grover et al.
While physical link protection schemes have the advantage of restoring links transparently and without regard to the type of user traffic on the links themselves, physical layer protection schemes have a high cost since they require unused spare links to be provisioned in anticipation of possible failures. On the other hand, the network recovery mechanism provided by the routing protocols alone such as OSPF is too slow to satisfy the service needs of networks that offer highly reliable services and are not acceptable in many practical situations.
Accordingly, there is a need for the development of an improved packet network and a method therefor which would avoid the aforementioned problems and provide an efficient and fast method distribution of node related information, e.g. in order to recover from link and node failures.